package array

func copyRandomList(head *Node) *Node {
	cachedNode := map[*Node]*Node{}
	var deepCopy func(node *Node) *Node 
	deepCopy = func(node *Node) *Node {
		if node == nil {
			return nil
		}
		if n, has := cachedNode[node]; has {
			return n
		}
		newNode := &Node{Val: node.Val}
		cachedNode[node] = newNode
		newNode.Next = deepCopy(node.Next)
		newNode.Random = deepCopy(node.Random)
		return newNode
	}
	return deepCopy(head)
}

type Node struct {
	Val int
	Next *Node
	Random *Node
}